leetcode 89.Gray Code（格雷码）

原题传送门—>>



题目描述：

格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。
给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。即使有多个不同答案，你也只需要返回其中一种。
格雷编码序列必须以 0 开头。

示例1：

输入: 2
输出: [0,1,3,2]
解释:
00 - 0
01 - 1
11 - 3
10 - 2
对于给定的 n，其格雷编码序列并不唯一。
例如，[0,2,3,1] 也是一个有效的格雷编码序列。
00 - 0
10 - 2
11 - 3
01 - 1

示例2:

输入: 0
输出: [0]
解释: 我们定义格雷编码序列必须以 0 开头。
给定编码总位数为 n 的格雷编码序列，其长度为 2n。当 n = 0 时，长度为 20 = 1。
因此，当 n = 0 时，其格雷编码序列为 [0]。

一道背答案的题,记录一下.
我先参考了下面这篇文章:
原文链接:格雷码Gray Code详解

• 第一步，改变最右边的位元值；
  
• 第二步，改变右起第一个为1的位元的左边位元；
  
• 第三步，第四步重复第一步和第二步，直到所有的格雷码产生完毕（换句话说，已经走了(2^n) - 1 步）。
  

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> ans;
        if(!n)
        {
            ans.push_back(0);
            return ans;
        }
        int count = (1 << (n-1));//共需要生成2*count个数字,循环count次
        int num = 0;
        for(int i = 0; i < count; ++i)
        {
            ans.push_back(num);
            num ^= 1;
            ans.push_back(num);
            change(num);
        }
        return ans;
    }
    void change(int &n)//改变n右起第一个为‘1’的位的左位
    {
        int i = 1;
        int flag = 0;
        while(!flag)//flag为1时退出循环
        {
            flag = n & i;
            i = i << 1;
        }
        n = n ^ i;
    }
};

该方案仅仅击败了40% ,看到题解中有套更好的算法:
原文链接:Gray Code （镜像反射法，图解）

所以用这种思想我又重写了代码:

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> ans;
        ans.push_back(0);
        for(int i = 0; i < n; ++i)
        {
            int start = ans.size() - 1;
            for(int j = start; j >= 0; --j)
            {
                ans.push_back(ans[j] + (1 << i));
            }
        }
        return ans;
    }
};

果然100%kill